BOJ_1197_최소 스패닝 트리

최소 스패닝 트리(MST)를 구하는 문제
최소 스패닝 트리를 구하는 알고리즘에는 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있는데, 간선이 적은 경우가 아니라면 대체로 정점 위주의 프림 알고리즘이 유용하기 때문에 프림 알고리즘으로 풀었다

단순 너비 우선 탐색(BFS)의 방문 처리와 프림 알고리즘의 방문 처리는 사뭇 다르다.
BFS에서 Node를 담는 것은 한 번이면 족하기 때문에 연결되어 있는 노드를 확인하는 반복문 안에서 방문 처리를 하는 것이 Queue에 추가적으로 노드를 담지 않게 해 유용한 반면, 프림 알고리즘에서는 목적지가 같은 노드라도 비용이 다를 수 있기 때문에 같은 목적지의 노드가 여러 번 Queue에 담길 수 있다. 따라서 반복문 내부에서 방문 처리를 하지 않으며 Priority Queue에서 정렬된 노드를 뽑았을 때 방문처리를 해줘야 올바르게 작동한다.

package BJO;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJO_1197_최소스패닝트리 {

    static int V;
    static int E;

    static List<Node>[] list;

    static int total = 0;

    static class Node implements Comparable<Node> {
        int to;
        int value;

        Node(int to, int value) {
            this.to = to;
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        list = new ArrayList[V + 1];

        for (int i = 1; i < V + 1; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            // C는 음수일 수도 있음
            int C = Integer.parseInt(st.nextToken());
            list[A].add(new Node(B, C));
            list[B].add(new Node(A, C));
        }

        Queue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[V + 1];

        pq.offer(new Node(1, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (visited[node.to]) {
                continue;
            }

            visited[node.to] = true;
            total += node.value;


            for (int i = 0; i < list[node.to].size(); i++) {
                Node next = list[node.to].get(i);

                if (!visited[next.to]) {
                    pq.offer(next);
                }
            }
        }

        System.out.println(total);
    }
}